import Graph from '../../data-structures/graph';
import StackObject from '../../data-structures/stack-object';

enum Colors {
    WHITE = 0, // 没被访问过
    GREY = 1, // 被访问过一次，处于待第二次访问状态
    BLACK = 2, // 完全探索完（它的邻接顶点都被访问了一次）
}

/**
 * 初始化图里所有顶点的颜色，白色（没被访问过）
 */
const initializeColor = (vertices: Array<string | number>): { [key: string]: Colors } => {
    const color: { [key: string]: Colors } = {};
    for (let i = 0, vl = vertices.length; i < vl; i ++) {
        color[vertices[i]] = Colors.WHITE;
    }
    return color;
};

/**
 * 深度优先遍历(DFS)，并在每个点遍历完后回调
 * 不使用调用栈的方式
 */
export const depthFirstSearch = (graph: Graph, startVertex: string | number = null, callBack: Function) => {
    const vertices: Array<string | number> = graph.getVertices(); // 所有顶点
    const adjList: Map<string | number, Array<string | number>> = graph.getAdjList(); // 顶点与邻接顶点
    const color: { [key: string]: Colors } = initializeColor(vertices); // 初始化所有顶点的颜色

    if (startVertex != null && vertices.includes(startVertex)) { // 开始点存在并且是该图里的顶点
        depthFirstSearchVisit(startVertex, adjList, color, callBack);
    } else { // 没有开始点就从vertices的0下标开始
        for (let i = 0, vl = vertices.length; i < vl; i ++) {
            if (color[vertices[i]] === Colors.WHITE) { // 未访问的
                depthFirstSearchVisit(vertices[i], adjList, color, callBack);
            }
        }
    }
};

const depthFirstSearchVisit = (
    startVertex: string | number,
    adjList: Map<string | number, Array<string | number>>,
    color: { [key: string]: Colors },
    callBack: Function,
) => {
    const stack = new StackObject<string | number>(); // 待访问列表是栈结构的
    color[startVertex] = Colors.GREY; // 开始点只会被访问一次，所以要事先置为灰色，后面被访问完就置为黑色
    stack.push(startVertex); // 开始点

    while (!stack.isEmpty()) { // 栈为空就结束
        let u: string | number = stack.peek(); // 查看栈顶的顶点，暂时不弹出
        let neighbors: Array<string | number> = adjList.get(u); // 它所有邻接顶点
        if (neighbors.length > 0) {
            neighbors = neighbors.filter(vertex => color[vertex] === Colors.WHITE); // 只留白色的临界点
        }
        if (neighbors.length > 0) {// 还存在没有被访问过的邻接顶点
            color[neighbors[0]] = Colors.GREY; // 始终取第一个，这是第一次访问
            stack.push(neighbors[0]); // 因为访问了一次，要等待第二次访问，所以放入栈顶
        } else { // 没有可访问的邻接顶点，代表这条路径走完了
            u = stack.pop(); // 将当前顶点弹出，准备遍历新顶点
            color[u] = Colors.BLACK; // 完全探索完
            if (callBack) { // 完全被探索完就回调
                callBack(u);
            }
        }
    }
};

/**
 * 深度优先遍历(DFS)，并在每个点遍历完后回调
 * 使用调用栈的方式
 */
export const depthFirstSearch1 = (graph: Graph, startVertex: string | number, callBack: Function) => {
    const vertices: Array<string | number> = graph.getVertices(); // 所有顶点
    const adjList: Map<string | number, Array<string | number>> = graph.getAdjList(); // 顶点与邻接顶点
    const color: { [key: string]: Colors } = initializeColor(vertices); // 初始化所有顶点的颜色

    color[startVertex] = Colors.GREY; // 开始点只有一次访问，所以事先置灰
    depthFirstSearchVisit1(color, startVertex, adjList, callBack); // 开始点

};
const depthFirstSearchVisit1 = (
    color: { [key: string]: Colors },
    u: string | number,
    adjList: Map<string | number, Array<string | number>>,
    callBack: Function,
) => {
    const neighbors: Array<string | number> = adjList.get(u); // 它所有邻接顶点
    for (let i = 0, nl = neighbors.length; i < nl; i ++) { // 遍历所有邻接顶点
        const w: string | number = neighbors[i];
        if (color[w] === Colors.WHITE) { // 白色的才能访问
            color[w] = Colors.GREY; // 白色变为灰色，被访问一次
            depthFirstSearchVisit1(color, w, adjList, callBack); // 入栈，递归形成调用栈
        }
    }
    color[u] = Colors.BLACK; // 完全被探索完，变为黑色
    if (callBack) { // 完全被探索完就回调
        callBack(u);
    }
};

/**
 * 使用深度优先遍历图，得出每个点距离开始点的发现时间和完全探索时间，还有他们之间的回溯点（具体路径）
 * 不使用调用栈的方式
 */
export const dfs = (graph: Graph, startVertex: string | number = null) => {
    const vertices: Array<string | number> = graph.getVertices(); // 所有顶点
    const adjList: Map<string | number, Array<string | number>> = graph.getAdjList(); // 顶点与邻接顶点
    const color: { [key: string]: Colors } = initializeColor(vertices); // 初始化所有顶点的颜色

    const d: { [key: string]: number } = {}; // 发现时间
    const f: { [key: string]: number } = {}; // 完全探索时间
    const p: { [key: string]: string | number } = {}; // 回溯点
    const time: { [key: string]: number } = { count: 0 }; // 时间计数器

    // 初始发现时间 完全探索时间 回溯点
    for (let i = 0, vl = vertices.length; i < vl; i ++) {
        d[vertices[i]] = 0;
        f[vertices[i]] = 0;
        p[vertices[i]] = null;
    }
    if (startVertex != null && vertices.includes(startVertex)) { // 开始点存在并且是该图里的顶点
        dfsVisit(startVertex, adjList, color, d, f, p, time);
    } else { // 没有开始点就从vertices的0下标开始
        for (let i = 0, vl = vertices.length; i < vl; i ++) {
            if (color[vertices[i]] === Colors.WHITE) { // 未访问的
                dfsVisit(vertices[i], adjList, color, d, f, p, time);
            }
        }
    }
    return { discovery: d, finished: f, predecessors: p };
};
const dfsVisit = (
    startVertex: string | number,
    adjList: Map<string | number, Array<string | number>>,
    color: { [key: string]: Colors },
    d: { [key: string]: number },
    f: { [key: string]: number },
    p: { [key: string]: string | number },
    time: { [key: string]: number } = { count: 0 },
) => {
    const stack = new StackObject<string | number>(); // 待访问列表
    d[startVertex] = ++ time.count; // 开始点第一次被发现的时间
    color[startVertex] = Colors.GREY; // 开始点只会被访问一次，所以要事先置为灰色，后面被访问完就置为黑色
    stack.push(startVertex); // 开始点

    while (!stack.isEmpty()) { // 栈为空就结束
        let u: string | number = stack.peek(); // 查看栈顶的顶点，暂时不弹出
        let neighbors: Array<string | number> = adjList.get(u); // 它所有邻接顶点
        if (neighbors.length > 0) {
            neighbors = neighbors.filter(vertex => color[vertex] === Colors.WHITE); // 只留白色的临界点
        }
        if (neighbors.length > 0) {// 还存在没有被访问过的邻接顶点
            const w: string | number = neighbors[0];
            d[w] = ++ time.count; // 第一次被发现的时间
            p[w] = u; // w的回溯点是u
            color[w] = Colors.GREY; // 始终只取第一个
            stack.push(w); // 置灰访问了一次，放入栈顶
        } else { // 没有可访问的邻接顶点，代表这条路径走完了
            u = stack.pop(); // 将当前顶点弹出栈，准备遍历新顶点
            f[u] = ++ time.count; // 完全探索完的时间
            color[u] = Colors.BLACK; // 完全探索完
        }
    }
};
/**
 * 深度优先遍历(DFS)，并在每个点遍历完后回调
 * 使用调用栈的方式
 */
export const dfs1 = (graph: Graph, startVertex: string | number = null) => {
    const vertices: Array<string | number> = graph.getVertices(); // 所有顶点
    const adjList: Map<string | number, Array<string | number>> = graph.getAdjList(); // 顶点与邻接顶点
    const color: { [key: string]: Colors } = initializeColor(vertices); // 初始化所有顶点的颜色

    const d: { [key: string]: number } = {}; // 发现时间
    const f: { [key: string]: number } = {}; // 完全探索时间
    const p: { [key: string]: string | number } = {}; // 回溯点
    const time: { [key: string]: number } = { count: 0 }; // 时间计数器

    // 初始发现时间 完全探索时间 回溯点
    for (let i = 0, vl = vertices.length; i < vl; i ++) {
        d[vertices[i]] = 0;
        f[vertices[i]] = 0;
        p[vertices[i]] = null;
    }
    if (startVertex != null && vertices.includes(startVertex)) { // 开始点存在并且是该图里的顶点
        dfsVisit1(startVertex, adjList, color, d, f, p, time); // 开始点
    } else { // 没有开始点就从vertices的0下标开始
        for (let i = 0, vl = vertices.length; i < vl; i ++) {
            if (color[vertices[i]] === Colors.WHITE) { // 未访问的
                dfsVisit1(vertices[i], adjList, color, d, f, p, time); // 开始点
            }
        }
    }
    return { discovery: d, finished: f, predecessors: p };
};
const dfsVisit1 = (
    u: string | number,
    adjList: Map<string | number, Array<string | number>>,
    color: { [key: string]: Colors },
    d: { [key: string]: number },
    f: { [key: string]: number },
    p: { [key: string]: string | number },
    time: { [key: string]: number } = { count: 0 },
) => {
    d[u] = ++ time.count; // 第一次被发现的时间
    color[u] = Colors.GREY; // 置为灰色
    const neighbors: Array<string | number> = adjList.get(u); // 它所有邻接顶点
    for (let i = 0, nl = neighbors.length; i < nl; i ++) { // 遍历所有邻接顶点
        const w: string | number = neighbors[i];
        if (color[w] === Colors.WHITE) { // 白色的才能访问
            p[w] = u; // w的回溯点是u
            dfsVisit1(w, adjList, color, d, f, p, time); // 入栈，递归形成调用栈
        }
    }
    f[u] = ++ time.count; // 完全探索完的时间
    color[u] = Colors.BLACK; // 完全被探索完，变为黑色
};
